Advances in mobile computing and embedded device technologies open up new computing environments. The environments contain numerous data generators such as sensors, probes and agents, which generate data in the form of continuous data stream. In order to monitor such data streams and take proper actions promptly, if needed, users register a large number of range queries or filters which are evaluated continuously. We call them continuous range queries. There have been extensive inventions on evaluating a large number of continuous range queries. However, they concentrate on processing Region Monitoring Queries (RMQs) rather than Border Monitoring Queries (BMQs). RMQ reports all matching data streams in a query range. However, BMQ only reports data streams coming into or going out from a query range.
Query indices have widely been used for shared evaluation of RMQs. We call such a query index a RMQ-Index. Upon each data arrival, matching queries are quickly determined by searching the query index. RMQ-Indices have been invented for one-dimensional and two-dimensional range queries. The indices proposed for 1-D range queries can again be categorized to a tree-based query index or a grid-based query index. The tree-based indices such as Interval Skip List (IS-list) have O(log N) search cost and O(N log N) storage cost, where N is the number of registered queries. Compared to the tree-based indices, the grid-based query index such as Containment Encoded Interval (CEI) has better search performance. There are also tree-based query indices as well as grid-based ones for 2-dimensional range queries. For 2-dimensional queries as well, the grid-based indices show much better search performance than the tree-based ones. However, the grid-based indices require much larger storage space since queries are redundantly inserted into multiple grids depending on query ranges. Generally, the grid-based indices for 2-dimensional consume larger storage space than those for 1-dimensional due to the increase in the number of grids.
Due to the semantic difference between RMQ and BMQ, the existing RMQ-Indices are generally not suitable for BMQs. If a RMQ-Index is used for BMQ evaluation, costly post-processing is required to sort out only the border-crossing data streams. Thus, the performance becomes considerably low compared to that of our invention, which is specifically designed for efficient BMQ evaluation.